package com.cet.programmercarl.algorithmperformancanalysis.栈与队列;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @program: algorithm
 * @description: 滑动窗口最大值
 * @author: 陈恩涛
 * @create: 2022-07-12 15:36
 **/
public class LC239 {

    public static void main(String[] args) {
        final int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
//        for (int i : maxSlidingWindow1(nums, 3)) {
//            System.out.println(i);
//        }

        for (int i : maxSlidingWindow3(nums, 3)) {
            System.out.println(i);
        }

    }

    public static int[] maxSlidingWindow1(int[] nums, int k) {
        if (k > nums.length) {
            throw new RuntimeException("窗口太大！");
        }
        final Deque<Integer> deque = new LinkedList<>();
        int maxEndIndex = k - 1;
        for (int i = 0; i < k; i++) {
            deque.addFirst(nums[i]);
        }
        final int length = nums.length;
        for (int i = k; i < length; i++) {
            final Integer lastValue = deque.removeLast();
            deque.addFirst(nums[i]);
            if (lastValue < nums[i]) {
               maxEndIndex = i;
            }
        }
        return Arrays.copyOfRange(nums, maxEndIndex - k, maxEndIndex);
    }

    /**
     * 单调队列解决滑动窗口最大值
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSlidingWindow2(int[] nums, int k) {
        // 维护一个单调队列（数组元素的下标）
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        int n = nums.length;
        int[] res = new int[n - k + 1];
        int idx = 0;
        for(int i = 0; i < n; i++) {
            // 根据题意，i为nums下标，是要在[i - k + 1, i] 中选到最大值，只需要保证两点
            // 1.队列头结点需要在[i - k + 1, i]范围内，不符合则要弹出
            while(!deque.isEmpty() && deque.peek() < i - k + 1){
                deque.poll();
            }
            // 2.既然是单调，就要保证每次放进去的数字要比末尾的都大，否则也弹出
            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            deque.offer(i);

            // 因为单调，当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了
            if(i >= k - 1){
                res[idx++] = nums[deque.peek()];
            }
        }
        return res;
    }

    public static int[] maxSlidingWindow3(int[] nums, int k) {
        // 样本数组长度
        final int length = nums.length;
        final Deque<Integer> deque = new ArrayDeque<>();
        final int[] result = new int[length - k + 1];
        for (int i = 0; i < length; i++) {

            // poll元素时，若等于队头元素，则出队，否则不操作队列
            if (!deque.isEmpty() && deque.peek() == nums[i]) {
                deque.pop();
            }

            // push元素时，如果push的元素value大于入口元素的数值，
            // 那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止
            while (!deque.isEmpty() && nums[i] > deque.peekLast()) {
                deque.pollLast();
            }

            deque.addLast(nums[i]);

            if (i >= k - 1) {
                result[i - k + 1] = deque.peek();
            }
        }
        return result;
    }

}
